package 动态规划.完全背包;

/**
 * 题意概要：区别于01背包就是每种物品可以选取无数次
 */
public class Solution {

    public int backPackII(int m, int[] w, int[] v) {
        // write your code here
        // dp[i][j]   -> 装前面i个物品的时候, 容量为j的最大价值
        // dp[i][j] = Math.max(dp[i-1][j], dp[i][j-weight] + value) 这样就可以选无数次了
        int n = w.length;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (j < w[i]) {// 不能塞的时候也不能硬塞，要注意一下
                    dp[i][j] = dp[i-1][j];
                }
                else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-w[i]] + v[i]);
                }
            }
        }
        return dp[n][m];
    }

}
